package com.algorithm.sort;

/**
 * @program: 快速排序
 * @author: luhd
 * @create: 2021-08-10
 */
public class QuickSort {
    public static void main(String[] args) {
        /**
         * 快速排序使用分治法来把一个串（list）分为两个子串
         * 从数列中挑出一个元素，称为 “基准”（pivot）；
         * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）
         * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
         */
        int [] arr = {15,5,3,7,9 ,2,18,10,20,6};
        QuickSort(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }

    /**
     *     运用分治算法，通过基准元素将数组分为两部分，分散在基准元素两边，无限细分，最后有序
     * @param arr   待排序数组
     * @param start    起始位置数组下标
     * @param end   最后位置数组下标
     * @return  方法就是找基准元素，最后返回的是有序的数组
     */
    public static int[] QuickSort(int[] arr, int start, int end){  //  start=0   end=arr.length-1
        if(arr.length<1 || start<0 || end>= arr.length || start > end) return null;
        int smallIndex = partition(arr, start, end);    //获取基准元素的下标位置,基准元素的下标位置一定是准确的，即不会被影响，当获取到大部分基准元素下标的时候，数组就是有序的
        if(smallIndex > start) QuickSort(arr, start, smallIndex-1);   //递归，继续获取基准元素的下标(-1是去掉基准元素本身)
        if(smallIndex < end) QuickSort(arr, smallIndex+1, end);   //递归，继续获取基准元素的下标(+1是去掉基准元素本身)
        return arr;
    }
    public static int partition(int[] arr, int start, int end){
        int pivot = start;  //将起始位置的第一个值作为基准元素
        int index = pivot+1;  //从基准元素的后一位起，都与基准元素的值比较大小
        for (int i = index; i <=end ; i++) {    //为什么可以等于end？  end是length-1，即数组的最后一位数值的下标
            if(arr[i]<arr[pivot]){
                swap(arr,i,index);   //为什么是和index交换位置？ index可以理解为从左向右移动的指针，找到比基准元素小的值的时候，交换位置，指针右移
                index++;    //当有值小于基准元素时，index++，，即index代表的是比基准元素小的数值的最大的数组下标，即基准元素的数组下标的前一位
            }
        }
        swap(arr,pivot,index-1);   //这里的index-1，是因为上面的index++，将基准元素的值换到正确的位置，这个值换到数组的最前面(这个值满足比基准元素小的条件)
        return index-1;     //返回的是基准元素的下标
    }

    /**
     *  交换数组中两个元素的位置
     */
    public static void swap(int[] arr ,int i ,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
